home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / gnu / libg_261.zip / libg_261 / libg++ / src / BitSet.h < prev    next >
C/C++ Source or Header  |  1994-05-11  |  9KB  |  375 lines
  1. // This may look like C code, but it is really -*- C++ -*-
  2. /* 
  3. Copyright (C) 1988 Free Software Foundation
  4.     written by Doug Lea (dl@rocky.oswego.edu)
  5.  
  6. This file is part of the GNU C++ Library.  This library is free
  7. software; you can redistribute it and/or modify it under the terms of
  8. the GNU Library General Public License as published by the Free
  9. Software Foundation; either version 2 of the License, or (at your
  10. option) any later version.  This library is distributed in the hope
  11. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  12. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  13. PURPOSE.  See the GNU Library General Public License for more details.
  14. You should have received a copy of the GNU Library General Public
  15. License along with this library; if not, write to the Free Software
  16. Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  17. */
  18.  
  19. #ifndef _BitSet_h
  20. #ifdef __GNUG__
  21. #pragma interface
  22. #endif
  23.  
  24. #define _BitSet_h 1
  25.  
  26. #include <iostream.h>
  27. #include <limits.h>
  28.  
  29. #define BITSETBITS  (sizeof(short) * CHAR_BIT)
  30.  
  31. struct BitSetRep
  32. {
  33.   unsigned short  len;          // number of shorts in s
  34.   unsigned short  sz;           // allocated slots
  35.   unsigned short  virt;         // virtual 0 or 1
  36.   unsigned short  s[1];         // bits start here
  37. };
  38.  
  39. extern BitSetRep*   BitSetalloc(BitSetRep*, const unsigned short*, 
  40.                                 int, int, int);
  41. extern BitSetRep*   BitSetcopy(BitSetRep*, const BitSetRep*);
  42. extern BitSetRep*   BitSetresize(BitSetRep*, int);
  43. extern BitSetRep*   BitSetop(const BitSetRep*, const BitSetRep*, 
  44.                              BitSetRep*, char);
  45. extern BitSetRep*   BitSetcmpl(const BitSetRep*, BitSetRep*);
  46.  
  47.  
  48. extern BitSetRep    _nilBitSetRep;
  49.  
  50. class BitSet;
  51.  
  52. class BitSetBit
  53. {
  54. protected:
  55.   BitSet*            src;
  56.   unsigned long      pos;
  57.  
  58.  public:
  59.                      BitSetBit(BitSet* v, int p);
  60.                      BitSetBit(const BitSetBit& b);
  61.                     ~BitSetBit();
  62.                      operator int() const;
  63.   int                operator = (int b);
  64.   int                operator = (const BitSetBit& b);
  65. };
  66.  
  67. class BitSet
  68. {
  69. protected:
  70.   BitSetRep*          rep;
  71.  
  72.   
  73. public:
  74.  
  75. // constructors
  76.                      BitSet();
  77.                      BitSet(const BitSet&);
  78.  
  79.                     ~BitSet();
  80.  
  81.   BitSet&            operator =  (const BitSet& y);
  82.  
  83. // equality & subset tests
  84.  
  85.   friend int         operator == (const BitSet& x, const BitSet& y);
  86.   friend int         operator != (const BitSet& x, const BitSet& y);
  87.   friend int         operator <  (const BitSet& x, const BitSet& y);
  88.   friend int         operator <= (const BitSet& x, const BitSet& y);
  89.   friend int         operator >  (const BitSet& x, const BitSet& y);
  90.   friend int         operator >= (const BitSet& x, const BitSet& y);
  91.  
  92.  
  93. // operations on self
  94.  
  95.   BitSet&            operator |= (const BitSet& y);
  96.   BitSet&            operator &= (const BitSet& y);
  97.   BitSet&            operator -= (const BitSet& y);
  98.   BitSet&            operator ^= (const BitSet& y);
  99.  
  100.   void               complement();
  101.  
  102. // individual bit manipulation
  103.  
  104.   void               set(int pos);
  105.   void               set(int from, int to);
  106.   void               set(); // set all
  107.  
  108.   void               clear(int pos);
  109.   void               clear(int from, int to);
  110.   void               clear(); // clear all
  111.  
  112.   void               invert(int pos);
  113.   void               invert(int from, int to);
  114.  
  115.   int                test(int pos) const;
  116.   int                test(int from, int to) const;
  117.  
  118.   BitSetBit          operator [] (int i);
  119.   
  120. // iterators
  121.  
  122.   int                first(int b = 1) const;
  123.   int                last(int b = 1) const;
  124.  
  125.   int                next(int pos, int b = 1) const;
  126.   int                prev(int pos, int b = 1) const;
  127.   int                previous(int pos, int b = 1) const /* Obsolete synonym */
  128.     { return prev(pos, b); }
  129.  
  130. // status
  131.  
  132.   int                empty() const;
  133.   int                virtual_bit() const;
  134.   int                count(int b = 1) const;
  135.   
  136. // convertors & IO
  137.  
  138.   friend BitSet      atoBitSet(const char* s, 
  139.                                char f='0', char t='1', char star='*');
  140.   // BitSettoa is deprecated; do not use in new programs.
  141.   friend const char* BitSettoa(const BitSet& x, 
  142.                                char f='0', char t='1', char star='*');
  143.  
  144.   friend BitSet      shorttoBitSet(unsigned short w);
  145.   friend BitSet      longtoBitSet(unsigned long w);
  146.  
  147.   friend ostream&    operator << (ostream& s, const BitSet& x);
  148.   void             printon(ostream& s,
  149.                  char f='0', char t='1', char star='*') const;
  150.  
  151. // procedural versions of operators
  152.  
  153.   friend void        and(const BitSet& x, const BitSet& y, BitSet& r);
  154.   friend void        or(const BitSet& x, const BitSet& y, BitSet& r);
  155.   friend void        xor(const BitSet& x, const BitSet& y, BitSet& r);
  156.   friend void        diff(const BitSet& x, const BitSet& y, BitSet& r);
  157.   friend void        complement(const BitSet& x, BitSet& r);
  158.  
  159. // misc
  160.  
  161.   void      error(const char* msg) const;
  162.   int                OK() const;
  163. };
  164.  
  165.  
  166. typedef BitSet BitSetTmp;
  167.  
  168.  
  169.   BitSet      operator |  (const BitSet& x, const BitSet& y);
  170.   BitSet      operator &  (const BitSet& x, const BitSet& y);
  171.   BitSet      operator -  (const BitSet& x, const BitSet& y);
  172.   BitSet      operator ^  (const BitSet& x, const BitSet& y);
  173.  
  174.   BitSet      operator ~  (const BitSet& x);
  175.  
  176. // These are inlined regardless of optimization
  177.  
  178. inline int BitSet_index(int l)
  179. {
  180.   return (unsigned)(l) / BITSETBITS;
  181. }
  182.  
  183. inline int BitSet_pos(int l)
  184. {
  185.   return l & (BITSETBITS - 1);
  186. }
  187.  
  188.  
  189. inline BitSet::BitSet() : rep(&_nilBitSetRep) {}
  190.  
  191. inline BitSet::BitSet(const BitSet& x) :rep(BitSetcopy(0, x.rep)) {}
  192.  
  193. inline BitSet::~BitSet() { if (rep != &_nilBitSetRep) delete rep; }
  194.  
  195. inline BitSet& BitSet::operator =  (const BitSet& y)
  196. { 
  197.   rep = BitSetcopy(rep, y.rep);
  198.   return *this;
  199. }
  200.  
  201. inline int operator != (const BitSet& x, const BitSet& y) { return !(x == y); }
  202.  
  203. inline int operator >  (const BitSet& x, const BitSet& y) { return y < x; }
  204.  
  205. inline int operator >= (const BitSet& x, const BitSet& y) { return y <= x; }
  206.  
  207. inline void and(const BitSet& x, const BitSet& y, BitSet& r)
  208. {
  209.   r.rep =  BitSetop(x.rep, y.rep, r.rep, '&');
  210. }
  211.  
  212. inline void or(const BitSet& x, const BitSet& y, BitSet& r)
  213. {
  214.   r.rep =  BitSetop(x.rep, y.rep, r.rep, '|');
  215. }
  216.  
  217. inline void xor(const BitSet& x, const BitSet& y, BitSet& r)
  218. {
  219.   r.rep =  BitSetop(x.rep, y.rep, r.rep, '^');
  220. }
  221.  
  222. inline void diff(const BitSet& x, const BitSet& y, BitSet& r)
  223. {
  224.   r.rep =  BitSetop(x.rep, y.rep, r.rep, '-');
  225. }
  226.  
  227. inline void complement(const BitSet& x, BitSet& r)
  228. {
  229.   r.rep = BitSetcmpl(x.rep, r.rep);
  230. }
  231.  
  232. #if defined(__GNUG__) && !defined(_G_NO_NRV)
  233.  
  234. inline BitSet operator & (const BitSet& x, const BitSet& y) return r
  235. {
  236.   and(x, y, r);
  237. }
  238.  
  239. inline BitSet operator | (const BitSet& x, const BitSet& y) return r
  240. {
  241.   or(x, y, r);
  242. }
  243.  
  244. inline BitSet operator ^ (const BitSet& x, const BitSet& y) return r
  245. {
  246.   xor(x, y, r);
  247. }
  248.  
  249. inline BitSet operator - (const BitSet& x, const BitSet& y) return r
  250. {
  251.   diff(x, y, r);
  252. }
  253.  
  254. inline BitSet operator ~ (const BitSet& x) return r
  255. {
  256.   ::complement(x, r);
  257. }
  258.  
  259. #else /* NO_NRV */
  260.  
  261. inline BitSet operator & (const BitSet& x, const BitSet& y) 
  262. {
  263.   BitSet r; and(x, y, r); return r;
  264. }
  265.  
  266. inline BitSet operator | (const BitSet& x, const BitSet& y) 
  267. {
  268.   BitSet r; or(x, y, r); return r;
  269. }
  270.  
  271. inline BitSet operator ^ (const BitSet& x, const BitSet& y) 
  272. {
  273.   BitSet r; xor(x, y, r); return r;
  274. }
  275.  
  276. inline BitSet operator - (const BitSet& x, const BitSet& y) 
  277. {
  278.   BitSet r; diff(x, y, r); return r;
  279. }
  280.  
  281. inline BitSet operator ~ (const BitSet& x) 
  282. {
  283.   BitSet r; ::complement(x, r); return r;
  284. }
  285.  
  286. #endif
  287.  
  288. inline BitSet& BitSet::operator &= (const BitSet& y)
  289. {
  290.   and(*this, y, *this);
  291.   return *this;
  292. }
  293.  
  294. inline BitSet& BitSet::operator |= (const BitSet& y)
  295. {
  296.   or(*this, y, *this);
  297.   return *this;
  298. }
  299.  
  300. inline BitSet& BitSet::operator ^= (const BitSet& y)
  301. {
  302.   xor(*this, y, *this);
  303.   return *this;
  304. }
  305.  
  306. inline BitSet& BitSet::operator -= (const BitSet& y)
  307. {
  308.   diff(*this, y, *this);
  309.   return *this;
  310. }
  311.  
  312.  
  313. inline void BitSet::complement()
  314. {
  315.   ::complement(*this, *this);
  316. }
  317.  
  318. inline int BitSet::virtual_bit() const
  319. {
  320.   return rep->virt;
  321. }
  322.  
  323. inline int BitSet::first(int b) const
  324. {
  325.   return next(-1, b);
  326. }
  327.  
  328. inline int BitSet::test(int p) const
  329. {
  330.   if (p < 0) error("Illegal bit index");
  331.   int index = BitSet_index(p);
  332.   return (index >= rep->len)? rep->virt : 
  333.          ((rep->s[index] & (1 << BitSet_pos(p))) != 0);
  334. }
  335.  
  336.  
  337. inline void BitSet::set()
  338. {
  339.   rep = BitSetalloc(rep, 0, 0, 1, 0);
  340. }
  341.  
  342. inline BitSetBit::BitSetBit(const BitSetBit& b) :src(b.src), pos(b.pos) {}
  343.  
  344. inline BitSetBit::BitSetBit(BitSet* v, int p)
  345. {
  346.   src = v;  pos = p;
  347. }
  348.  
  349. inline BitSetBit::~BitSetBit() {}
  350.  
  351. inline BitSetBit::operator int() const
  352. {
  353.   return src->test(pos);
  354. }
  355.  
  356. inline int BitSetBit::operator = (int b)
  357. {
  358.   if (b) src->set(pos); else src->clear(pos); return b;
  359. }
  360.  
  361. inline int BitSetBit::operator = (const BitSetBit& b)
  362. {
  363.   int i = (int)b;
  364.   *this = i;
  365.   return i;
  366. }
  367.  
  368. inline BitSetBit BitSet::operator [] (int i)
  369. {
  370.   if (i < 0) error("illegal bit index");
  371.   return BitSetBit(this, i);
  372. }
  373.  
  374. #endif
  375.